//
// Created by yanhai on 2021/1/10.
//

/**
 * 判断两个链表是否交叉
 * 并获取交叉点
 */

#include <stdio.h>
#include "link_common.h"

/**
 * 判断两个链表是否相交
 * 原理：判断两个链表里面的最后一个节点是否是同一个即可。
 * @param T1
 * @param T2
 * @return
 */
bool link_intersect_check(link *T1, link *T2)
{
    if (!T1->root || !T2->root)
        return false;

    link_node *last_node1 = T1->root;
    link_node *last_node2 = T2->root;

    while (last_node1->next) {
        last_node1 = last_node1->next;
    }
    while (last_node2->next) {
        last_node2 = last_node2->next;
    }

    return last_node1 == last_node2;
}

/**
 * 确定两个链表的交叉点 - 暴力算法
 * 原理：指向T1第1个元素，依次遍历T2所有元素，相比较，如果有相等，则表示有相交，该节点就是相交点
 *      指向T1第2个元素，重复上面的操作。
 *      直至T1遍历结束，都没有发现有相同的点，则表示没有相交。
 * 时间复杂度：
 *    T1长度为m， T2长度为n，则为O(m*n)
 * @param T1
 * @param T2
 * @return NULL：没有交叉
 */
link_node *link_intersect_detect1(link *T1, link *T2)
{
    link_node *t1 = T1->root;
    link_node *t2;

    while (t1 != NULL) {
        t2 = T2->root;

        while (t2 != NULL) {
            if (t1 == t2)
                return t1;
            t2 = t2->next;
        }

        t1 = t1->next;
    }
    return NULL;
}

/**
 * 确定两个链表的交叉点 - 方法2：
 * 原理：由于链表相交只存在Y型相交，不存在X型相交，意思就是如果相交，2个链表从相交点开始后面的是重合的。
 *      这样，在已知两个链表长度的情况下(m和n)，让较长的链表先向后移动(m-n)次，
 *      此时再开始依次比较两个链表相互对应的节点是否是同一个，如果不同，则两个链表同时向后移动1位，再进行比较
 *      如果到最后都没有相同的节点，则表示没有相交。
 * 时间复杂度：
 *      T1长度为m， T2长度为n，假设m>=n
 *      计算T1和T2的长度，是m+n次
 *      然后T1移动m-n次
 *      然后最坏情况下比较了n次
 *      因此 (m+n)+(m-n)+n = 2m+n = O(m+n)
 * @param T1
 * @param T2
 * @return
 */
link_node *link_intersect_detect2(link *T1, link *T2)
{
    int m = 0;  // T1的长度
    int n = 0;  // T2的长度

    link_node *t1 = T1->root;
    link_node *t2 = T2->root;

    // 计算T1的长度
    while (t1 != NULL) {
        m++;
        t1 = t1->next;
    }
    // 计算T2的长度
    while (t2 != NULL) {
        n++;
        t2 = t2->next;
    }

    if (m == 0 || n == 0) {
        return NULL;
    }

    // 令较长的为t1，较短的为t2
    if (m >= n) {
        t1 = T1->root;
        t2 = T2->root;
    } else {
        t1 = T2->root;
        t2 = T1->root;
    }

    // t1先后移m-n步
    for (int i = 0; i < m - n; i++) {
        t1 = t1->next;
    }

    // 对位相比较
    while (t1 != NULL) {
        if (t1 == t2) {
            return t1;
        }
        t1 = t1->next;
        t2 = t2->next;
    }

    return NULL;
}

/**
 * 测试是否交叉
 * @param T1
 * @param T2
 */
void link_intersect_check_test(link *T1, link *T2)
{
    if (link_intersect_check(T1, T2)) {
        printf("%s: T1 和 T2 有交叉\n", __FUNCTION__);
    } else {
        printf("%s: T1 和 T2 没有交叉\n", __FUNCTION__);
    }
}

/**
 * 测试获取交叉点
 * @param T1
 * @param T2
 * @param func 要测试的函数地址
 * @param func_name 函数名称，仅打印使用
 */
void link_intersect_detect_test(link *T1, link *T2,
                                link_node *(*func)(link *, link *),
                                const char *func_name)
{
    link_node *node = func(T1, T2);
    if (node == NULL) {
        printf("%s [%s]: T1 和 T2 没有交叉\n", __FUNCTION__, func_name);
    } else {
        printf("%s [%s]: T1 和 T2 的交叉点元素值为：%d\n", __FUNCTION__, func_name, node->key);
    }
}

/**
 * 打印2个链表
 * @param T1
 * @param T2
 * @param message
 */
void print_two_link(const link *T1, const link *T2, const char *message)
{
    printf("\n====== %s\n", message);
    printf("T1  ");
    link_print(T1);
    printf("T2  ");
    link_print(T2);
}

int main()
{
#define str(x) #x

    link T1 = link_create_from_index(20, false);
    link T2 = link_create_from_index(7, false);

    ////////////////////////// 相交前 ///////////////////
    print_two_link(&T1, &T2, "相交前");

    link_intersect_check_test(&T1, &T2);
    link_intersect_detect_test(&T1, &T2, link_intersect_detect1, str(link_intersect_detect1));
    link_intersect_detect_test(&T1, &T2, link_intersect_detect2, str(link_intersect_detect2));

    //////////////////////// 使相交 /////////////////////
    // 将T1的中的元素值为14的节点追加到T2链表
    link_node *node = link_find(&T1, 14);
    assert(node != NULL);
    link_append(&T2, node);

    //////////////////////// 相交后 /////////////////////
    print_two_link(&T1, &T2, "相交后");

    link_intersect_check_test(&T1, &T2);
    link_intersect_detect_test(&T1, &T2, link_intersect_detect1, str(link_intersect_detect1));
    link_intersect_detect_test(&T1, &T2, link_intersect_detect2, str(link_intersect_detect2));

    // todo 销毁有交叉的2个链表，
    //  方法1：先分别销毁交叉点前的节点，再销毁交叉点及其后面的节点
    //  方法2：让其中1条链表的交叉点前的节点的next为NULL，再对2条链表正常释放
//    link_destroy(&T1);
//    link_destroy(&T2);
    return 0;
}
